package InterviewTest.q0406_inorderSuccessor;

import CommonClass.Common.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution_1 {
    /*
    直接使用中序遍历
    在中序遍历的过程中维护上一个访问的节点和当前访问的节点。
    如果上一个访问的节点是节点 p，则当前访问的节点即为节点 p 的后继节点
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {

        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode prev = null, curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev == p) {
                return curr;
            }
            prev = curr;
            curr = curr.right;
        }
        return null;

    }
}
